/*
 * algo.h
 *
 *  Created on: Sep 25, 2014
 *      Author: lucas
 */

#define M_PI	3.14159265358979323846
#define EPS		1e-5
typedef unsigned int uint;

typedef struct Polynomial
{
	double *p;
	int size;
} Polynomial;

struct SplitPolynomial
{
	struct Polynomial high;
	struct Polynomial low;
	int split;
};

struct Z
{
	struct Polynomial z2;
	struct Polynomial z1;
	struct Polynomial z0;
	int split;
};

int nextPowerOfTwo (int n);
double * paddedVector (double *p, int originalSize);
void nextPowerTester (void);
Polynomial createPolynomial (int size);
void freePolynomial (Polynomial p);
void printDoubles (int size, double *p);
void printPolynomial (Polynomial P);
void ioHandler (void);
void complexTest(void);
complex * doubleToComplex (double *p, int size, int biggerSize);
double * complexToDouble (complex *p, int size);
complex* copyCVec (complex * v, int N);
double * copyVec (double * v, int N);
complex * computeP1 (complex * p, int N);
complex * computeP2 (complex * p, int N);
void vecScale (complex * v, int N, int scale);
void printComplex (complex p);
void printComplexVec(complex *p, int n);
void DFTTest (void);
complex * recDFT (complex * p, int N);
complex * recIDFT (complex * p, int N);
complex * evaluateDFT (double * p, int N);
complex * pointwiseMult (complex * p1, complex * p2, int N);
double * quad_algo (int n, double * p1, double * p2);
double * fft_algo (int n, double * p1, double * p2);
double * karat_algo (int n, double * p1, double * p2);
int split_size (int N);
struct SplitPolynomial split (int N, int split_point, struct Polynomial p);
void sub_coeff (struct Polynomial x, struct Polynomial y);
void add_coeff (struct Polynomial x, struct Polynomial y);
struct Polynomial _sub_coeff (struct Polynomial x, struct Polynomial y);
struct Polynomial _add_coeff (struct Polynomial x, struct Polynomial y);
Polynomial shiftPoly (Polynomial p, int amount);
struct Polynomial compose_poly (struct Z zees);
struct Z computeZ (struct SplitPolynomial X, struct SplitPolynomial Y);
struct Polynomial karat_core (int n, struct Polynomial x, struct Polynomial y);
void multpoli_quad(int n, double A[], double B[], double C[]);
void multpoli_kara(int n, double A[], double B[], double C[]);
void multpoli_fft (int n, double A[], double B[], double C[]);
